//试除法判定质数
bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i <= n / i;i ++){ //优化内容
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
//分解质因数，时间复杂度(sqrt(n))
//根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。
//n=p1^a1 * p2^a2 *p3^a3.....pn^an
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;//i为质数，s为质数的幂
        }
    if (x > 1) cout << x << ' ' << 1 << endl;//n中最多只含有一个大于sqrt(n)的因子，如果n还是>1，说明这就是大于sqrt(n)的唯一质因子
}
//质因子最多有 logx 个
//线性筛质数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(){
    for(int i = 2;i <= n;i ++){
        if(!st[i]) primes[cnt ++]=i;
        for(int j = 0;primes[j] <= n / i; j++)
        {
            st[primes[j] * i]=true;
            if(i % primes[j]==0) break;
        }
    }
}

//通过线性筛可以筛出所有质数，在多次操作时比直接分解质因数快
for(int i = 0; i <= cnt - 1; i ++)
{
    if(k % primes[i] == 0)
    {
        yinsu.push_back(primes[i]);
        while(k % primes[i] ==0)
        {
            k /= primes[i];
        }
    }
    if(primes[i] > k || k == 1)
    {
        break;
    }
    if(vis[k] == 1)//如果这个数是质数，vis表示是质数的数
    {
        yinsu.push_back(k);
        break;
    }
}